package interview.dfs;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 出城路径 https://blog.codefun2000.com/company/hw/23-4-19/P1196.html
 */
public class ExitCityPath {

    /**
     * 思路：回溯遍历所有路径，找到一条合法路径后比较更新最优路径。注意先对每一层的节点进行排序，保证回溯时先遍历较小路径
     */
    static List<Integer>[] childList;
    static Deque<Integer> resultPath;
    static HashSet<Integer> set = new HashSet<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        childList = new ArrayList[n];
        for (int i = 0;i < n;i++) {
            childList[i] = new ArrayList<>();
        }
        int m = sc.nextInt();
        for (int i = 0;i < m;i++) {
            childList[sc.nextInt()].add(sc.nextInt());
        }
        for (int i = 0;i < n;i++) {
            Collections.sort(childList[i]);//先对每一层的节点进行排序，保证回溯时先遍历较小路径
        }
        int d = sc.nextInt();
        for (int i = 0;i < d;i++)
            set.add(sc.nextInt());
        Deque<Integer> curPath = new ArrayDeque<>();
        curPath.add(0);
        recur(curPath, 0);
        if (resultPath == null) System.out.println("NULL");//看清题目，要考虑没有路径的情况
        else System.out.println(resultPath.stream().map(Objects::toString).collect(Collectors.joining("->")));
    }

    public static void recur(Deque<Integer> curPath, int root) {
        if (childList[root].size() == 0) {
            if (resultPath == null || resultPath.size() > curPath.size())
                resultPath = new ArrayDeque<>(curPath);
            return;
        }
        for (Integer child : childList[root]) {
            if (set.contains(child)) continue;
            curPath.add(child);
            recur(curPath, child);
            curPath.removeLast();
        }
    }
}
